package dmsxl.zhanyuduilie;

import java.util.*;

/**
 * Author: Zhang Dongwei
 * Date: 2023/5/4 19:07
 * 滑动窗口最大值
 */
public class zydl7_239 {

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        System.out.println(Arrays.toString(maxSlidingWindow(nums, k)));
    }

//    暴力，超时
    public static int[] maxSlidingWindow1(int[] nums, int k) {
        int[] res = new int[nums.length-k+1];
        for (int i = k - 1; i < nums.length; i++){
            int tempmax = nums[i];
            for (int j = i - k + 1; j < i; j++){
                if (nums[j] > tempmax){
                    tempmax = nums[j];
                }
            }
            res[i-k+1] = tempmax;
        }
        return res;
    }

//    题解1：自定义数组，效率还行
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums.length == 1){
            return nums;
        }
        int len = nums.length - k + 1;
        int[] res = new int[len];
        int num = 0;
        MyQueue1 myQueue1 = new MyQueue1();
        for (int i = 0; i < k; i++){
            myQueue1.add(nums[i]);
        }
        res[num++] = myQueue1.peek();
        for (int i = k; i < nums.length; i++){
            myQueue1.poll(nums[i - k]);
            myQueue1.add(nums[i]);
            res[num++] = myQueue1.peek();
        }
        return res;
    }

    //题解2：利用双端队列手动实现单调队列，效率较好
    /**
     * 用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可
     * 单调队列类似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右边为头结点，元素存的是下标)
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int idx = 0;
        for(int i = 0; i < n; i++) {
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while(!deque.isEmpty() && deque.peek() < i - k + 1){
                deque.poll();
            }
            // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offer(i);

            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if(i >= k - 1){
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }

}

class MyQueue1{
    Deque<Integer> deque = new LinkedList<>();

    void poll(int val){
        if (!deque.isEmpty() && deque.peek()==val){
            deque.poll();
        }
    }

    void add(int val){
        while (!deque.isEmpty() && val > deque.getLast()){
            deque.removeLast();
        }
        deque.add(val);
    }

    int peek(){
        return deque.peek();
    }
}

